ABC147E Balanced Path

题解：

方格？取数？向右向下走？

我首先很自然地想到了f[i][j]表示到(i,j)格最小差的dp，然鹅这是错的，因为这玩意显然是不满足局部最优解的。。。

注意到每个格上的数给的很小，只有80，这意味差的绝对值范围只在0~161x80（161意思是在80x80的棋盘里，要走过161格）

然后考虑f[i][j][k]=0/1表示到第(i,j)格，差的绝对值为k的方案是否存在

转移时枚举f[i-1][j][]和f[i][j-1][]中的所有可行的k（可行的判定即f[i][j][k]=1），加上或减去当前格内的差值，记为k’，将所有的f[i][j][|k’|]赋为1（注意绝对值）

这里发现转移有很多多余的步骤，所以可以添加一点优化

讲一下我选择的优化，优化幅度较小，但代码好打，即额外额外一个g[i][j]表示当前各自上可行解得最大值，这样转移时就不用每次的从0到161x80跑，只需要0到g[i][j-1]和g[i-1][j]就可以了

其它人的优化也是异曲同工，主要目的是减少冗余的试错

因为最后答案既要满足最优，又要满足可行，所以$ans= \min \{ k|f[n][m][k]==1 \}$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=82;
int n,m,a[N][N],b[N][N],g[N][N];
bool f[N][N][12801];

signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            read(a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            read(b[i][j]),a[i][j]=abs(a[i][j]-b[i][j]); //反正只需要一个差，就先都算出来
    f[1][1][a[1][1]]=1;
    g[1][1]=a[1][1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(i>1){
                for(int k=0;k<=g[i-1][j];k++) if(f[i-1][j][k])
                    f[i][j][abs(k-a[i][j])]=f[i][j][k+a[i][j]]=1;
                g[i][j]=max(g[i][j],g[i-1][j]+a[i][j]);
            }
            if(j>1){
                for(int k=0;k<=g[i][j-1];k++) if(f[i][j-1][k])
                    f[i][j][abs(k-a[i][j])]=f[i][j][k+a[i][j]]=1;
                g[i][j]=max(g[i][j],g[i][j-1]+a[i][j]);
            }
        }
    for(int k=0;k<=g[n][m];k++) if(f[n][m][k]){
        write(k);
        return 0;
    }
}